Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time
Identifieur interne : 002731 ( Main/Exploration ); précédent : 002730; suivant : 002732Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time
Auteurs : Mouhammad Said [France] ; Jacques-Olivier Lachaud [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: We address the problem of computing the exact characteristics of any subsegment of a digital straight line with known characteristics. We present a new algorithm that solves this problem, whose correctness is proved. Its principle is to climb the Stern-Brocot tree of fraction in a bottom-up way. Its worst-time complexity is proportionnal to the difference of depth of the slope of the input line and the slope of the output segment. It is thus logarithmic in the coefficients of the input slope. We have tested the effectiveness of this algorithm by computing a multiscale representation of a digital shape, based only on a digital straight segment decomposition of its boundary.
Url:
DOI: 10.1007/978-3-642-19867-0_27
Affiliations:
- France
- Auvergne (région administrative), Auvergne-Rhône-Alpes, Rhône-Alpes
- Aubière, Le Bourget du Lac
- Université Savoie Mont Blanc
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003264
- to stream Istex, to step Curation: 003223
- to stream Istex, to step Checkpoint: 000631
- to stream Main, to step Merge: 002773
- to stream Main, to step Curation: 002731
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time</title><author><name sortKey="Said, Mouhammad" sort="Said, Mouhammad" uniqKey="Said M" first="Mouhammad" last="Said">Mouhammad Said</name></author><author><name sortKey="Lachaud, Jacques Olivier" sort="Lachaud, Jacques Olivier" uniqKey="Lachaud J" first="Jacques-Olivier" last="Lachaud">Jacques-Olivier Lachaud</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D49DB5B187D9E0774661A04B98495CB5F2A343F5</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-19867-0_27</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-NK4R3GTT-Z/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003264</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003264</idno><idno type="wicri:Area/Istex/Curation">003223</idno><idno type="wicri:Area/Istex/Checkpoint">000631</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000631</idno><idno type="wicri:doubleKey">0302-9743:2011:Said M:computing:the:characteristics</idno><idno type="wicri:Area/Main/Merge">002773</idno><idno type="wicri:Area/Main/Curation">002731</idno><idno type="wicri:Area/Main/Exploration">002731</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time</title><author><name sortKey="Said, Mouhammad" sort="Said, Mouhammad" uniqKey="Said M" first="Mouhammad" last="Said">Mouhammad Said</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Mathématiques, UMR 5127 CNRS, Université de Savoie, 73376, Le Bourget du Lac</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Le Bourget du Lac</settlement></placeName><orgName type="university">Université Savoie Mont Blanc</orgName></affiliation><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>IUT, LAIC, Univ. Clermont-Ferrand, Campus des Cézeaux, 63172, Aubière Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Auvergne (région administrative)</region><settlement type="city">Aubière</settlement></placeName></affiliation></author><author><name sortKey="Lachaud, Jacques Olivier" sort="Lachaud, Jacques Olivier" uniqKey="Lachaud J" first="Jacques-Olivier" last="Lachaud">Jacques-Olivier Lachaud</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Mathématiques, UMR 5127 CNRS, Université de Savoie, 73376, Le Bourget du Lac</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Le Bourget du Lac</settlement></placeName><orgName type="university">Université Savoie Mont Blanc</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We address the problem of computing the exact characteristics of any subsegment of a digital straight line with known characteristics. We present a new algorithm that solves this problem, whose correctness is proved. Its principle is to climb the Stern-Brocot tree of fraction in a bottom-up way. Its worst-time complexity is proportionnal to the difference of depth of the slope of the input line and the slope of the output segment. It is thus logarithmic in the coefficients of the input slope. We have tested the effectiveness of this algorithm by computing a multiscale representation of a digital shape, based only on a digital straight segment decomposition of its boundary.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Auvergne (région administrative)</li><li>Auvergne-Rhône-Alpes</li><li>Rhône-Alpes</li></region><settlement><li>Aubière</li><li>Le Bourget du Lac</li></settlement><orgName><li>Université Savoie Mont Blanc</li></orgName></list><tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Said, Mouhammad" sort="Said, Mouhammad" uniqKey="Said M" first="Mouhammad" last="Said">Mouhammad Said</name></region><name sortKey="Lachaud, Jacques Olivier" sort="Lachaud, Jacques Olivier" uniqKey="Lachaud J" first="Jacques-Olivier" last="Lachaud">Jacques-Olivier Lachaud</name><name sortKey="Lachaud, Jacques Olivier" sort="Lachaud, Jacques Olivier" uniqKey="Lachaud J" first="Jacques-Olivier" last="Lachaud">Jacques-Olivier Lachaud</name><name sortKey="Said, Mouhammad" sort="Said, Mouhammad" uniqKey="Said M" first="Mouhammad" last="Said">Mouhammad Said</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002731 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002731 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:D49DB5B187D9E0774661A04B98495CB5F2A343F5
|texte= Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time
}}
| This area was generated with Dilib version V0.6.33. |  |